定義
n(n>=0)個節點組成的有限集合,一個節點最多有兩個子樹
空二元樹
該集合為空集合
二元樹的五種型態
空樹
跟節點
跟節點+左子樹
跟節點+右子樹
跟節點+左子樹+右子樹
滿二元樹
葉節點都在同一層
非葉節點的分支都是2
完全二元樹
同一個序號節點的要與滿二元樹的該序號節點位置相同
(完全二元樹不一定是滿二元樹,滿二元樹一定是完全二元樹)
葉節點只能出現在最下兩層
最下層的葉子集中在左半部連續位置
倒數第二層如果有葉節點則集中在右半部連續位置
如果節點分支為1,則只有左子節點
性質
第i層最多有2^(i-1)個節點
深度為k最多有(2^k)-1個節點
任何一個二元樹,葉節點樹為n0,分支為2的節點為n2,則n0 = n2 +1
具有n個節點的完全二元樹的深度為 log2(N) + 1
iThome鐵人賽
看影片追技術